package Test_1127;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    public static class TreeNode{
        public char val;//数据
        public TreeNode left;//左孩子
        public TreeNode right;//右孩子
        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode createTree(){
        //创建节点
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        //连接节点
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        return A;
    }
//判断是否相同的树：
    //结构是否相同：
    //结构可能出现的三种情况：
    //1.节点都为null，该情况结构相同
    //2.p的节点为null，q的节点不为null；或者q的节点为null，p的节点不为null，该情况结构不同
    //3.节点都不为null,说明结构相同
    //那么值是否相同：
    //那么这个是两个节点之间的结构进行比较，我们还要看其左右子树是否相同
    public boolean isSameTree1(TreeNode p, TreeNode q) {
        //结构是否相同：
        //结构可能出现的三种情况：
        //1.节点都为null
        if(p==null && q==null){
            return true;
        }
        //2.p的节点为null，q的节点不为null；或者q的节点为null，p的节点不为null
        if(p==null && q!=null ||q==null && p!=null ){
            return false;
        }
        //前两种结构已经判断，剩下最后一种就是都不为空，如果都不为空，说明结构相同
        //那我们要判断值相不相同
        if(p.val!=q.val){
            return false;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
    //判断相同的情况：
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //结构是否相同：
        //结构可能出现的三种情况：
        //1.节点都为null
        if(p==null && q==null){
            return true;
        }
        //直接判断相同：
        if(p!=null && q!=null && q.val==p.val){
            return true;
        }
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
    //另一棵子树的子树:
    //1.判断是不是根的子树；
    //2.判断是不是左子树的子树；
    //3.判断是不是右子树的子树；
    //总之：判断与根、左、右子树是不是相同的树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //首先判断节点是不是为null
        if(root==null){
            return false;
        }
        //1.判断是不是根的子树；
        if(isSameTree(root,subRoot)){
            return true;
        }
        //2.判断是不是左子树的子树；
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        //3.判断是不是右子树的子树；
        if(isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }
    //翻转二叉树:就是将左右子树进行翻转
    public TreeNode invertTree(TreeNode root) {
           if(root==null){
               return null;
           }
           //将左右子树进行交换
           TreeNode tmp=root.left;
           root.left=root.right;
           root.right=tmp;
           //递归左右子树
           invertTree(root.left);
           invertTree(root.right);
           return root;
    }
//判断平衡二叉树：
    public boolean isBalanced(TreeNode root) {
        //判断有无根节点
        if(root==null){
            return true;
        }
       // 算出左右子树的高度；
        int leftheight=height(root.left);
        int rightheight=height(root.right);
        //左右子树的高度相差的绝对值是否小于等于1。
        return Math.abs(leftheight-rightheight)<=1 &&isBalanced(root.left)&& isBalanced((root.right));
    }
    //获取高度：取左子树和右子树中的最大高度
    public int  height(TreeNode root){
          if(root==null){
              return 0;
          }
          int leftHeight=height(root.left);
          int rightHeight=height(root.right);
          return Math.max(leftHeight,rightHeight)+1;
    }
    //对称二叉树
    /*判断有无根节点，如果没有那么也是轴对称图形；
    判断左右子树是否对称：
    判断左子树的左子树与右子树的右子树是否相同；
    判断右子树的左子树与左子树的右子树是否相同；*/
    public boolean isSymmetric(TreeNode root) {
        //判断有无根节点，如果没有那么也是轴对称图形；
       if(root==null){
           return true;
       }
       //判断左右子树是否对称，
       return isSymmetricChild(root.left,root.right);
    }
    //判断左右子树是否对称：(原理同判断是否是一棵相同的树同理)
    //判断结构是否相同
    //值是否相同
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
        //左右节点都为null
        if(leftTree==null && rightTree==null){
            return true;
        }
        //左节点为null，右节点不为null；右节点为null，左节点不为null
        if(leftTree==null && rightTree!=null||leftTree!=null && rightTree==null){
            return false;
        }
        //都不为null，判断值是否相同
        if(leftTree.val!=rightTree.val){
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right)
                && isSymmetricChild(leftTree.right,rightTree.left);
    }
    }
